package other.yht;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 功能描述：Q47：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
 *
 * 注意：
 *
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 *
 *
 * 示例 1：
 *
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 示例 2：
 *
 * 输入：s = "a", t = "a"
 * 输出："a"
 * 示例 3:
 *
 * 输入: s = "a", t = "aa"
 * 输出: ""
 * 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
 * 因此没有符合条件的子字符串，返回空字符串。
 * 你能设计一个在 o(n) 时间内解决此问题的算法吗？
 *
 * @Author: yht
 * @Date: 2021/8/17 9:10
 */
public class MinLengthStr {

  /**
   * 最佳结果一定是以B中其中一个字符开始，另一个字符结束的字符串片段
   * 那么就找出每一个可能的字符串，然后去比较长度
   * 遍历字符串A，每到B中存在的字符，就创建一个新的数组M以该字符位开始，同时创造一个和B一样的字符串C，
   * 将其中相同的那个字符删掉
   * 遇到下一个字符A【i】时，检查C，假如C中存在该字符，就在M记录下i的值，在C中删除字符A【i】
   * 当C被删到空时，M中也集齐了符合条件的一个组合。如果到最后C还没删完，则M不符合条件
   * 然后把一堆符合条件的数组拿出来比各自最大值最小值跨度
   * 找出其中最小的即是最符合的
   * 应该是最优方法了
   *
   * @param a
   * @param b
   */
  void getShortestStr(String a, String b) {
    List<String> strs = new ArrayList<>();
    List<List<Integer>> tt = new ArrayList<>();
    //遍历大字符串
    for(int i = 0; i < a.length(); i++) {
      char f = a.charAt(i);
      //如果该字符在小字符串中存在
      int bi = b.indexOf(f);
      if(bi != -1) {
        //在历史集合中添加一个
        strs.add(b);
        tt.add(new ArrayList<>());
        //遍历历史字符串集合
        for(int j = 0; j < strs.size(); j++) {
          String js = strs.get(j);
          int index = js.indexOf(f);
          if(index != -1) {
            strs.set(j, js.replaceFirst(String.valueOf(f),""));
            tt.get(j).add(i);
          }
        }
      }
    }
    String bestComb = "";
    String bestStr = "";
    int shortestLen = a.length();

    for(int j = 0; j < strs.size(); j++) {
      String js = strs.get(j);
      //该位置的组合已完成
      if(js.length() == 0) {
        List<Integer> success = tt.get(j);
        int min = success.get(0), max = success.get(0);
        for(int t : success) {
          if(t < min) min = t;
          if(t > max) max = t;
        }
        String comb = Arrays.toString(success.toArray());
        String str = a.substring(min, max+1);
        int len = max - min + 1 ;

//        System.out.println("下标组合：" + comb);
//        System.out.println("字符串：" + str);
//        System.out.println("长度：" + len);
//        System.out.println();

        if(len < shortestLen) {
          bestComb = comb;
          bestStr = str;
          shortestLen = len;
        }
      }
    }

//    if(bestComb.length() > 0) {
//      System.out.println("最佳下标组合：" + bestComb);
//      System.out.println("最佳字符窜：" + bestStr);
//      System.out.println("最短长度：" + shortestLen);
//      System.out.println();
//    }else {
//      System.out.println("不存在符合条件的组合");
//    }
  }

  /**
   * 使用了桶思想，创建一个和B一样大的桶，将A中符合条件的位置放到对应桶中
   * 再从每个桶中取出一个数字组成组合
   * 最后比较每种组合，选出最优解
   * @param a
   * @param b
   */
  void getMin(String a, String b){
    int [][] tongs = new int[b.length()][a.length()];
    for(int i = 0; i < a.length(); i++) {
      int site = b.indexOf(a.charAt(i));
      if(site != -1) {
        int[] tong = tongs[site];
        for(int j = 0; j < tong.length; j++){
          if(tong[j] == 0) {
            tong[j] = i + 1;
            break;
          }
        }
      }
    }
    for(int m = 0; m < tongs.length; m++) {
      if(tongs[m][0] == 0) {
        tongs[m] = tongs[b.indexOf(String.valueOf(b.charAt(m)))];
      }
    }
    List<List<Integer>> res = comb(tongs);

    int shortest = a.length();
    String shortestStr = "";

    for(List<Integer> list : res) {
      int min = a.length();
      int max = -1;
      boolean qualified = true;
      loop:
      for(int i = 0; i < list.size(); i++) {
        int tmp = list.get(i);
        for(int j = 0; j < i; j++) {
          if(tmp == list.get(j)) {
            qualified = false;
            break loop;
          }
        }
        if(tmp < min) min = tmp;
        if(tmp > max) max = tmp;
      }
      if(qualified && (shortest > (max - min + 1))) {
        shortest = max - min + 1;
        shortestStr = a.substring(min - 1, max);
      }
    }

//    System.out.println(shortestStr);
//    System.out.println(shortest);
  }

  private List<List<Integer>> comb(int [][] tongs) {
    List<List<Integer>> res = new ArrayList<>();
    int [] zt = tongs[0];
    for(int j=0; j<zt.length; j++) {
      if( zt[j] == 0) break;
      List<Integer> zero = new ArrayList<>();
      zero.add(zt[j]);
      res.add(zero);
    }
    for(int point = 1; point < tongs.length; point++) {
      List<List<Integer>> newres = new ArrayList<>();
      int [] tong = tongs[point];
      for(int i=0; i<res.size(); i++) {
        List<Integer> resi = res.get(i);
        for(int j=0; j<tong.length; j++) {
          if(tong[j] == 0) break;
          List<Integer> resi2 = new ArrayList<>(resi);
          resi2.add(tong[j]);
          newres.add(resi2);
        }
      }
      res = newres;
    }
    return res;
  }

  public static void main(String[] args) {
    MinLengthStr m = new MinLengthStr();
    String a = "afahthjygtdsafahadjyk打发我回家大VA股我vdkuavcyw"
        + "adcauaywdvaycatwcdfdagdwasfawsadwaasadwafsdawfaswgaafsadwafwfafwawaasg";
    String b = "aasgh打";

    long start = System.currentTimeMillis();
    for(int i = 0; i<10000; i++) {
//      m.getMin(a,b);
    m.getShortestStr(a,b);
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);

  }
}
